//给定一个整数数组 A，返回其中元素之和可被 K 整除的（连续、非空）子数组的数目。 
//
// 
//
// 示例： 
//
// 输入：A = [4,5,0,-2,-3,1], K = 5
//输出：7
//解释：
//有 7 个子数组满足其元素之和可被 K = 5 整除：
//[4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]
// 
//
// 
//
// 提示： 
//
// 
// 1 <= A.length <= 30000 
// -10000 <= A[i] <= 10000 
// 2 <= K <= 10000 
// 
// Related Topics 数组 哈希表 前缀和 
// 👍 297 👎 0

  
package com.zwy.leetCode.editor.cn;
public class SubarraySumsDivisibleByK{
    public static void main(String[] args) {
        Solution solution = new SubarraySumsDivisibleByK().new Solution();
        int []A ={4,5,0,-2,-3,1};
        int K = 5;
        solution.subarraysDivByK(A,K);
      }
      //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int subarraysDivByK(int[] nums, int k) {
        int step=1;
        int count=0;
        int []p=new int[nums.length];
        p[0]=nums[0];
        for (int i = 1; i < nums.length; i++) {
            p[i]=p[i-1]+nums[i];
        }
        while(step<nums.length){
            for (int i = 0; i < nums.length-step; i++) {
                if(Math.abs(p[i]-p[i+step])%k==0)count++;
            }
            step++;
        }
        return count;
    }

}
//leetcode submit region end(Prohibit modification and deletion)

}